/*
 * @lc app=leetcode.cn id=18 lang=java
 *
 * [18] 四数之和
 */

// @lc code=start
class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        /*看起来像15,16题合起来的问题。。
        这样子需要两个base了，另外分类里的hash-table没有用到
        还是双指针法*/
        List<List<Integer>> lists = new ArrayList<>();
        //排序
        Arrays.sort(nums);
        int len = nums.length;
        for(int i = 0;i < len;++i) {

            if(i > 0 && nums[i] == nums[i-1]) continue;//防止重复解被写入

            for(int j = i+1;j<len;j++){

                if(j > i+1 && nums[j] == nums[j-1]) continue;//防止重复解被写入


                int L = j+1 , R= len -1;
                while(L<R){
                    int temp = nums[i]+nums[j]+nums[L]+nums[R];
                    if(temp == target){
                        List<Integer> list = new ArrayList<>();
                        list.add(nums[i]);
                        list.add(nums[j]);
                        list.add(nums[L]);
                        list.add(nums[R]);
                        lists.add(list);
                        while(L < R && nums[L+1] == nums[L]) ++L;
                        while (L < R && nums[R-1] == nums[R]) --R;//跳过重复解
                        //相等之后同时放缩，避免重复解
                        ++L;
                        --R;
                    }else if(temp -target < 0) {//说明temp小，L右移来增大temp
                        ++L;
                    } else {
                        --R;
                    }
                }

            }



        }

        return lists;
    }
}
// @lc code=end

